package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

class PalindromeLinkedList {
    public static void main(String[] args) {
        Solution solution = new PalindromeLinkedList().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        // 复制到数组中，时间复杂度O(n) = n，空间复杂度O(n) = n
        /*public boolean isPalindrome(ListNode head) {
            ListNode cur = head;
            List<Integer> list = new ArrayList<>();
            while (cur != null) {
                list.add(cur.val);
                cur = cur.next;
            }

            int[] res = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                res[i] = list.get(i);
            }

            int left = 0, right = res.length - 1;
            while (left < right) {
                if (res[left] != res[right]) return false;
                left++;
                right--;
            }

            return true;
        }*/

        /*
        // 使用全局变量来记录前面节点
        ListNode frontNode;

        public boolean isPalindrome(ListNode head) {
            frontNode = head;
            return recursivelyCheck(head);
        }

        // 递归法，使用递归的特性，在回溯的时候进行判断
        // 时间复杂度O(n) = n，空间复杂度O(n) = n
        private boolean recursivelyCheck(ListNode currentNode) {
            // 先递归到最后
            if (currentNode != null) {
                // 如果下一个不满足回文，返回false
                if (!recursivelyCheck(currentNode.next)) {
                    return false;
                }
                // 此时相等，这个数不满足回文条件
                else if (frontNode.val != currentNode.val) {
                    return false;
                }
                // 前面的指针向后移动一位
                frontNode = frontNode.next;
                return true;
            } else {
                // 等于null，停止递归
                // 返回true是为了使上一个匹配
                return true;
            }
        }*/

        /*public boolean isPalindrome(ListNode head) {
            if (head == null) {
                return true;
            }

            // 先找到中间节点
            ListNode mid = endOfFirstHalf(head);
            // 在后面节点进行反转
            ListNode cur = reverseList(mid.next);

            // 此时进行回文判断
            ListNode p1 = head;
            ListNode p2 = cur;
            boolean result = true;
            while (result && p2 != null) {
                if (p1.val != p2.val) result = false;
                p1 = p1.next;
                p2 = p2.next;
            }

            // 此时可以反转回来（题目没有硬性要求，可做可不做）
            ListNode listNode = reverseList(cur);

            return result;
        }

        // 反转链表函数
        private ListNode reverseList(ListNode head) {
            ListNode pre = null;
            ListNode cur = head;
            while (cur != null) {
                ListNode tmp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = tmp;
            }

            return pre;
        }

        // 使用快慢指针，找到链表的中间节点，在进行反转
        private ListNode endOfFirstHalf(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }

            return slow;
        }*/

        // 递归后序遍历方法
        /*ListNode left;

        public boolean isPalindrome(ListNode head) {
            left = head;
            return traversal(head);
        }

        public boolean traversal(ListNode head) {
            if (head == null) return true;
            boolean res = traversal(head.next);
            res = res && (left.val == head.val);
            left = left.next;
            return res;
        }
*/

        // 递归的另一种写法
/*        ListNode pre = null;
        boolean flag = true;

        public boolean isPalindrome(ListNode head) {
            pre = head;
            compare(head);
            return flag;
        }

        public void compare(ListNode node) {
            if (node == null) return;
            compare(node.next);
            if (pre != node && pre.val != node.val) flag = false;
        }*/

        public ListNode reverse(ListNode node) {
            ListNode pre = null, cur = node;
            while (cur != null) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }

            return pre;
        }

        public boolean isPalindrome(ListNode head) {
            // 快慢指针找到中心
            ListNode fast = head, slow = head;
            while (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }

            // 反转中点之后的链表
            ListNode head1 = reverse(slow.next);
            slow.next = null;

            ListNode cur1 = head, cur2 = head1;
            boolean flag = true;
            while (cur1 != null && cur2 != null) {
                if (cur1.val != cur2.val) {
                    flag = false;
                    break;
                }
                cur1 = cur1.next;
                cur2 = cur2.next;
            }

            // 反转回去
            slow.next = reverse(head1);

            return flag;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
